// 顺时针打印矩阵
//public class Printer {
//    public int[] clockwisePrint(int[][] mat, int n, int m) {
//        // 左上角 坐标
//        int x1 = 0;
//        int y1 = 0;
//        // 右下角坐标
//        int x2 = n - 1;
//        int y2 = m - 1;
//        int[] arr = new int[n * m];
//        int index = 0;
//        while(x1 <= x2 && y1 <= y2){
//            // 第一行： x1，y1 ~  y2
//            for(int i = y1;i <= y2;i++){
//                arr[index++] = mat[x1][i];
//            }
//            // 最后一列： x1 + 1 ~ x2， y2
//            for(int i = x1 +1;i <= x2;i++){
//                arr[index++] = mat[i][y2];
//            }
//            // 最后一行： x2， y2-1 ~ y1
//            if(x1 < x2){
//                for(int i = y2-1;i >= y1;i--){
//                    arr[index++] = mat[x2][i];
//                }
//            }
//            // 第一列： x2-1 ~ x1+1，y1
//            if(y1 < y2){
//                for(int i = x2-1;i >= x1+1;i--){
//                    arr[index++] = mat[i][y1];
//                }
//            }
//            x1++;
//            y1++;
//            y2--;
//            x2--;
//        }
//        return arr;
//    }
//}

//左右最值最大差
//public class MaxGap {
//    public int findMaxGap(int[] A, int n) {
//        int mx = A[0];
//        for(int i = 1;i < n;i++){
//            mx = Math.max(mx,A[i]);
//        }
//        return mx - Math.min(A[0],A[n-1]);
//    }
//}

//马戏团
//public class Main {
//
//    static class People {
//        int height;
//        int weight;
//
//        public People(int weight, int height) {
//            this.height = height;
//            this.weight = weight;
//        }
//    }
//
//    public static void main(String[] args) {
//
//        Scanner scan = new Scanner(System.in);
//        while (scan.hasNext()) {
//            int n = scan.nextInt();
//            People[] array = new People[n];
//            for (int i = 0; i < n; ++i) {
//                int index = scan.nextInt();
//                array[index - 1] = new People(scan.nextInt(), scan.nextInt());
//            }
//
//            Arrays.sort(array, new Comparator<People>() {
//                public int compare(People p1, People p2) {
//                    int result = Integer.compare(p1.height, p2.height);
//                    if (result != 0)
//                        return result;
//                    else
//                        return Integer.compare(p1.weight, p2.weight);
//                }
//            });
//
//            int[] dp = new int[n];
//            int max = Integer.MIN_VALUE;
//            for (int i = 0; i < dp.length; ++i) {
//                dp[i] = 1;
//                for (int j = i - 1; j >= 0; --j) {
//                    if (array[i].weight > array[j].weight
//                        || (array[i].weight == array[j].weight && array[i].height == array[j].height)) {
//                        dp[i] = Math.max(dp[i], dp[j] + 1);
//                    }
//                }
//                max = Math.max(dp[i], max);
//            }
//            System.out.println(max);
//        }
//    }
//}

// 合唱团
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int[] arr = new int[n+1];
//            for(int i = 1;i <= n;i++){
//                arr[i] = sc.nextInt();
//            }
//            int k = sc.nextInt();
//            int d = sc.nextInt();
//            long[][] fmax = new long[k+1][n+1];
//            long[][] fmin = new long[k+1][n+1];
//            long res = Integer.MIN_VALUE;
//            for(int i = 1;i <= n;i++){
//                fmax[1][i] = arr[i];
//                fmin[1][i] = arr[i];
//                for(int m = 2;m <= k;m++){
//                    for(int j = i - 1;j > 0 && i - j <= d;j--){
//                        fmax[m][i] = Math.max(fmax[m][i],Math.max(fmax[m-1][j] * arr[i],fmin[m-1][j] * arr[i]));
//                        fmin[m][i] = Math.min(fmin[m][i],Math.min(fmax[m-1][j] * arr[i],fmin[m-1][j] * arr[i]));
//                    }
//                }
//                res = Math.max(res,fmax[k][i]);
//            }
//            System.out.println(res);
//        }
//    }
//}

//简单错误记录
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        HashMap<String,Integer> map = new LinkedHashMap<>();
//        while(sc.hasNext()){
//            String str = sc.next();
//            int lineNum = sc.nextInt();
//            String[] arr = str.split("\\\\");
//            String s = arr[arr.length-1];
//            if(s.length() >  16){
//                s = s.substring(s.length() - 16);
//            }
//            String key = s + " " + lineNum;
//            if(map.containsKey(key)){
//                map.put(key,map.get(key)+1);
//            }else{
//                map.put(key,1);
//            }
//        }
//        int count = 0;
//        for(String str:map.keySet()){
//            count++;
//            if(count >map.keySet().size() - 8){
//                System.out.println(str + " " + map.get(str));
//            }
//        }
//    }
//}

// 数组中出现次数超过一半的数字
//public class Solution {
//    public int MoreThanHalfNum_Solution(int [] array) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for(int i = 0;i < array.length;i++){
//            map.put(array[i],map.containsKey(array[i])== false ? 1 : map.get(array[i])+1);
//        }
//        int res = -1;
//        for(int i = 0;i < array.length;i++){
//            if(map.get(array[i]) > (array.length/2)){
//                res = array[i];
//                break;
//            }
//        }
//        return res;
//    }
//}

//查找兄弟单词
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String[] words = new String[n];
//            for(int i = 0;i < n;i++){
//                words[i] = sc.next();
//            }
//            Arrays.sort(words);
//            String x = sc.next();
//            char[] charX = x.toCharArray();
//            Arrays.sort(charX);
//            int k = sc.nextInt();
//            int count = 0;
//            String res = "";
//            for(String str : words){
//                if(x.equals(str)){
//                    continue;
//                }
//                if(x.length() == str.length()){
//                    boolean flag = true;
//                    char[] charS = str.toCharArray();
//                    Arrays.sort(charS);
//                    for(int i = 0;i < charS.length;i++){
//                        if(charS[i] != charX[i]){
//                            flag = false;
//                            break;
//                        }
//                    }
//                    if(flag){
//                        count++;
//                        if(count == k){
//                            res = str;
//                        }
//                    }
//                }
//            }
//            if(count==0){
//                System.out.println(0);
//            }else{
//                System.out.println(count);
//                System.out.println(res);
//
//            }
//        }
//        sc.close();
//    }
//}

// 乒乓球筐
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            StringBuffer a = new StringBuffer(sc.next());
//            char[] b = sc.next().toCharArray();
//            boolean flag = true;
//            for(char c : b){
//                int index = a.indexOf(String.valueOf(c));
//                if(index!= -1){
//                    a.deleteCharAt(index);
//                }else{
//                    System.out.println("No");
//                    flag = false;
//                    break;
//                }
//            }
//            if(flag){
//                System.out.println("Yes");
//            }
//        }
//        sc.close();
//    }
//}

// 单词倒排
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        Stack<String> stack = new Stack<>();
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            StringBuffer s =  new StringBuffer();
//            for(int i = 0;i < str.length();i++){
//                char ch =  str.charAt(i);
//                if(Character.isLetter(ch)){
//                    s.append(ch);
//                }else{
//                    stack.push(new String(s));
//                    s = new StringBuffer();
//                }
//            }
//            stack.push(s.toString());
//            while(stack.size()>1){
//                System.out.print(stack.pop() + " ");
//            }
//            System.out.println(stack.pop());
//        }
//        sc.close();
//    }
//}

//骆驼命名法
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            StringBuffer s = new StringBuffer();
//            for(int i = 0;i < str.length();i++){
//                char ch = str.charAt(i);
//                if(ch == '_'){
//                    i++;
//                    ch = Character.toUpperCase(str.charAt(i));
//                }
//                s.append(ch);
//
//            }
//            System.out.println(s);
//        }
//        sc.close();
//    }
//}

// 求和
//public class Main {
//    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//    static ArrayList<Integer> list = new ArrayList<>();
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int m = sc.nextInt();
//            dfs(1,m,n);
//            for(ArrayList<Integer> l : res){
//                int i = 0;
//                for(;i < l.size()-1;i++){
//                    System.out.printf(l.get(i) + " ");
//                }
//                System.out.println(l.get(i));
//            }
//        }
//        sc.close();
//    }
//    public static void dfs(int index,int count,int n){
//        if(count == 0){
//            res.add(new ArrayList<>(list));
//        }else{
//            for(int i = index;i <= count && i <= n;i++){
//                list.add(i);
//                dfs(i+1,count-i,n);
//                list.remove(list.size()-1);
//            }
//        }
//
//    }
//}

//电话号码
//import java.util.*;
//import java.io.*;
//public class Main {
//    public static boolean isDigit(char ch){
//        return '0' <= ch && ch <= '9';
//    }
//    public static boolean isUpper(char ch){
//        return 'A'<= ch && ch <= 'Z';
//    }
//    public static void main(String[] args) throws Exception{
//        HashMap<Character,Character> map = new HashMap<>();
//        String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//        String num = "22233344455566677778889999";
//        char[] alphaArr = alpha.toCharArray();
//        char[] numArr = num.toCharArray();
//        for(int i =0;i < alphaArr.length;i++){
//            map.put(alphaArr[i],numArr[i]);
//        }
//        TreeSet<String> set = new TreeSet<>();
//        String line = null;
//        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//        while((line = reader.readLine()) != null){
//            set.clear();
//            int n = Integer.parseInt(line);
//            // 处理 n 个字符串
//            for(int i = 0; i < n;i++){
//                line = reader.readLine();
//                //保存转化之后的字符串
//                StringBuffer s = new StringBuffer();
//                char[] arr = line.toCharArray();
//                // 处理每一个字符
//                for(char ch : arr){
//                    if(isDigit(ch)){
//                        s.append(ch);
//                    }else if(isUpper(ch)){
//                        s.append(map.get(ch));
//                    }
//                }
//                // 调整格式：xxx-xxxx
//                line = s.substring(0,3) +"-" + s.substring(3);
//                // 保存结果
//                set.add(line);
//            }
//            // 打印传唤后之后的记过
//            for(String str : set){
//                System.out.println(str);
//            }
//            // 每组数据用空行隔开
//            System.out.println();
//        }
//    }
//
//}

//走迷宫
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            char[][] maze = new char[10][10];
//            int[][] map = new int[10][10];
//            for(int i = 0;i < 10;i++){
//                String s = sc.nextLine();
//                for(int j = 0;j < 10;j++){
//                    maze[i][j] = s.charAt(j);
//                    map[i][j] = Integer.MAX_VALUE;
//                }
//            }
//            map[0][1] = 0;
//            dfs(0,1,maze,map);
//            System.out.println(map[9][8]);
//
//        }
//        sc.close();
//    }
//    static int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};
//    public static void dfs(int row,int col,char[][] maze,int[][] map){
//        for(int i = 0;i < 4;i++){
//            int x= row + direction[i][0];
//            int y = col +direction[i][1];
//            while(x >= 0 && x < 10 && y >= 0 && y < 10 && maze[x][y] == '.' && map[x][y] > map[row][col]+1){
//                map[x][y] = map[row][col] + 1;
//                dfs(x,y,maze,map);
//            }
//        }
//    }
//}

// 解读密码
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            StringBuffer s = new StringBuffer();
//            for(int i = 0;i < str.length();i++){
//                char ch = str.charAt(i);
//                if(Character.isDigit(ch)){
//                    s.append(ch);
//                }
//            }
//            System.out.println(s);
//        }
//        sc.close();
//    }
//}

//Emacs计算器
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            String[] s = sc.nextLine().split(" ");
//            Stack<Integer> stack =  new Stack<>();
//            for(int i = 0;i < s.length;i++){
//                String ss =  s[i];
//                if(isOperator(ss)){
//                    int num2 = stack.pop();
//                    int num1 = stack.pop();
//                    switch(ss){
//                        case "+":
//                            stack.push( num1 + num2);
//                            break;
//                        case "-":
//                            stack.push(num1 - num2);
//                            break;
//                        case "*":
//                            stack.push(num1 * num2);
//                            break;
//                        case "/":
//                            stack.push(num1/num2);
//                            break;
//                    }
//                }else{
//                    stack.push(Integer.parseInt(ss));
//                }
//            }
//            System.out.println(stack.pop());
//        }
//        sc.close();
//    }
//    public static boolean isOperator(String s){
//        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) return true;
//        return false;
//    }
//}

// 五子棋
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            char[][] board = new char[20][20];
//            for(int i = 0;i<20;i++){
//                String str = sc.next();
//                for(int j = 0;j < 20;j++){
//                    board[i][j] = str.charAt(j);
//                }
//            }
//            if(check(board)){
//                System.out.println("Yes");
//            }else{
//                System.out.println("No");
//            }
//        }
//        sc.close();
//    }
//    static int[][] direction= {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
//    public static boolean check(char[][] board){
//        for(int i = 0;i < 20;i++){
//            for(int j = 0;j < 20;j++){
//                if(board[i][j] == '*' || board[i][j]== '+'){
//                    for(int k = 0;k < 8;k++){
//                        int count = 1;
//                        int x = i + direction[k][0];
//                        int y = j + direction[k][1];
//                        while(x >= 0 && x<20 && y >= 0 && y<20 && board[x][y] == board[i][j]){
//                            count++;
//                            x += direction[k][0];
//                            y += direction[k][1];
//                        }
//                        if(count >= 5){
//                            return true;
//                        }
//                    }
//                }
//            }
//        }
//        return false;
//    }
//}

//最长上升子序列
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0;i < n;i++){
//                arr[i] = sc.nextInt();
//            }
//            System.out.println(longest(arr,n));
//        }
//        sc.close();
//    }
//    public static int longest(int[] arr,int n){
//        int[] dp = new int[n];
//        dp[0]=1;
//        int max = 1;
//        for(int i = 1;i < n;i++){
//            dp[i] = 1;
//            for(int j = i-1;j >=0;j--){
//                if(arr[i] > arr[j]){
//                    dp[i] = Math.max(dp[i],dp[j]+1);
//                }
//            }
//            if(max < dp[i]){
//                max = dp[i];
//            }
//        }
//        return max;
//    }
//}

// 发邮件
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        long[] arr = new long[22];
//        arr[2] =1;
//        arr[3] =2;
//        for(int i = 4;i < 22;i++){
//            arr[i] = (i-1) * (arr[i-1] + arr[i-2]);
//        }
//        while(sc.hasNext()){
//            int n =  sc.nextInt();
//            System.out.println(arr[n]);
//        }
//        sc.close();
//    }
//}

//最长公共子序列
//public class Main {
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        while(in.hasNext()){
//            String s1=in.next();
//            String s2=in.next();
//            int[] dp=new int[s2.length()+1];
//            for(int i=0;i<s1.length();i++){
//                int pre=dp[0];
//                for(int j=1;j<=s2.length();j++){
//                    int temp=dp[j];
//                    if(s1.charAt(i)==s2.charAt(j-1))
//                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre+1));
//                    else
//                        dp[j]=Math.max(dp[j],Math.max(dp[j-1],pre));
//                    pre=temp;
//                }
//            }
//            System.out.println(dp[s2.length()]);
//        }
//        in.close();
//    }
//}


// 字符串计数
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            long ret = 0;
//            String s1 = sc.next();
//            String s2 = sc.next();
//            int len1 = sc.nextInt();
//            int len2 = sc.nextInt();
//            int maxLen = s1.length() > s2.length() ? s1.length() : s2.length();
//            int minLen = s1.length() > s2.length() ? s2.length() : s1.length();
//            for(int i = 0;i < maxLen;i++){
//                int distance;
//                if(i < minLen){
//                    distance = s2.charAt(i) - s1.charAt(i);
//                }else{
//                    if(s1.length() > s2.length()){
//                        distance = 'a' - s1.charAt(i) - 1;
//                    }else{
//                        distance = s2.charAt(i) - 'a' + 1;
//                    }
//                }
//                long now = 0;
//                for(int j = len1;j <= len2;j++){
//                    if(j - i -1 >= 0){
//                        now = now +(long)Math.pow(26,j-i-1);
//                    }
//                }
//                now =(now * distance)%1000007;
//                ret += now;
//            }
//            System.out.println(ret - 1);
//        }
//        sc.close();
//    }
//}

//蘑菇阵
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int m = sc.nextInt();
//            int k = sc.nextInt();
//            boolean[][] map = new boolean[n][m];
//            for(int i = 0;i < k;i++){
//                int x = sc.nextInt()-1;
//                int y = sc.nextInt()-1;
//                map[x][y] = true;
//            }
//            double[][] cw = new double[n][m];
//            cw[0][0] = 1;
//            for(int i = 0;i < n;i++){
//                for(int j = 0;j < m;j++){
//                    if(map[i][j]){
//                        cw[i][j] = 0;
//                    }else if(i == 0 && j == 0){
//
//                    }else{
//                        cw[i][j] = (j-1 < 0 ? 0 : (i+1 < n ? cw[i][j-1]*0.5 : cw[i][j-1]))+(i-1 < 0 ? 0 :(j + 1 < m ? cw[i-1][j]*0.5 : cw[i-1][j]));
//                    }
//                }
//            }
//            double res = cw[n-1][m-1];
//            System.out.println(String.format("%.2f",res));
//        }
//    }
//}

//红与黑
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int m = sc.nextInt();
//            int n = sc.nextInt();
//            char[][] arr = new char[m][n];
//            int indexX = 0;
//            int indenY = 0;
//            for(int i = 0;i < m;i++){
//                String s = sc.next();
//                for(int j = 0;j < n;j++){
//                    arr[i][j] = s.charAt(j);
//                    if('@' == arr[i][j]){
//                        indexX = i;
//                        indenY = j;
//                    }
//
//                }
//            }
//            boolean[][] flag = new boolean[m][n];
//            count = 0;
//            dfs(arr,m,n,indexX,indenY,flag);
//            System.out.println(count);
//
//        }
//        sc.close();
//    }
//    static int[][] direct = {{-1,0},{1,0},{0,-1},{0,1}};
//    static int count;
//    public static void dfs(char[][] map,int m,int n,int x,int y,boolean[][] flag){
//        if(flag[x][y]){
//            return;
//        }
//        if('#' == map[x][y]){
//            return;
//        }
//
//        count++;
//        flag[x][y] = true;
//
//        for(int i =0;i < 4;++i){
//            int nx = x + direct[i][0];
//            int ny = y + direct[i][1];
//            if(nx >=0 && nx < m && ny >=0 && ny< n){
//                dfs(map,m,n,nx,ny,flag);
//            }
//        }
//    }
//}

//数据库连接池
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int count = 0;
//            int max = 0;
//            for(int i = 0;i < n;i++){
//                String id = sc.next();
//                String s = sc.next();
//                if(s.equals("connect")){
//                    count++;
//                    if(max < count){
//                        max = count;
//                    }
//                }else if(s.equals("disconnect")){
//                    count--;
//                }
//            }
//            System.out.println(max);
//        }
//        sc.close();
//    }
//}


// mkdir
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            String[] arr = new String[n];
//            for(int i = 0;i < n;i++){
//                arr[i] = sc.next();
//            }
//            Arrays.sort(arr);
//            List<String> list = new ArrayList<>();
//            for(int i = 1;i < n;i++){
//                if(! arr[i].startsWith(arr[i-1] + "/")){
//                    list.add(arr[i-1]);
//                }
//            }
//            list.add(arr[n-1]);
//            for(String s : list){
//                System.out.println("mkdir -p " + s);
//            }
//            System.out.println();
//        }
//        sc.close();
//    }
//}

//Rational Arithmetic (20)
//import java.util.*;
//class Rational{
//    private long numerator;// 分子
//    private long denominator;// 分母
//    private long integer;// 整数部分
//    private boolean negetive;// 负数帕努单
//    private boolean isZero;// 分母为零
//    private long totalNumerator;// 最终参与运算的分子
//    public static long paraseNumerator(String s){
//        // 提取 分数的 分子
//        return Long.parseLong(s.substring(0,s.indexOf('/')));
//    }
//    public static long paraseDenominator(String s){
//        // 提取 分数的 分子
//        return Long.parseLong(s.substring(s.indexOf('/')+1));
//    }
//    Rational(long n,long d){
//        if(0 == d){
//            isZero = true;
//            return;
//        }
//        if(n < 0){
//            negetive = true;
//        }
//        if(d < 0){
//            negetive = !negetive;
//        }
//        // 如果输入的是假分数，需要将其调整为真分数，比如 5/3 == 1 2/3
//        integer = n/d;
//        numerator = n - integer * d;
//        denominator = Math.abs(d);
//
//        // 如果分数不是最简的形式，需要将其你约分为最简的形式，比如 10/15 == 2/3
//        // 在分子和分母的基础之上，分别处以分子和分母的最大公约数
//        if(numerator > 1 || numerator < -1){
//            long gcd = calcGCD(Math.abs(numerator),denominator);
//            if(gcd > 0){
//                numerator /= gcd;
//                denominator /= gcd;
//            }
//        }
//        totalNumerator = numerator + integer * denominator;
//    }
//    private long calcGCD(long a,long b){
//        if(b == 0){
//            return a;
//        }
//        return calcGCD(b,a%b);
//    }
//    public Rational add(Rational r){
//        long n = totalNumerator * r.denominator + denominator * r.totalNumerator;
//        long d = denominator * r.denominator;
//        return new Rational(n,d);
//    }
//    public Rational sub(Rational r){
//        long n = totalNumerator * r.denominator - denominator * r.totalNumerator;
//        long d = denominator * r.denominator;
//        return new Rational(n,d);
//    }
//    public Rational mul(Rational r){
//        long n = totalNumerator * r.totalNumerator;
//        long d = denominator * r.denominator;
//        return new Rational(n,d);
//    }
//    public Rational div(Rational r){
//        long n = totalNumerator * r.denominator;
//        long d = denominator * r.totalNumerator;
//        return new Rational(n,d);
//    }
//    public String toString(){
//        StringBuffer s = new StringBuffer();
//
//        if(isZero){
//            s.append("Inf");
//        }else if(integer == 0 && numerator == 0){
//            s.append("0");
//            return new String(s);
//        }
//        else{
//            if(negetive){
//                s.append("(-");
//            }
//            if(0 != integer){
//                s.append(Math.abs(integer));
//                if(numerator != 0){
//                    s.append(" ");
//                }
//            }
//            if(0 != numerator){
//                s.append(Math.abs(numerator));
//                s.append('/');
//                s.append(denominator);
//            }
//        }
//        if(negetive){
//            s.append(')');
//        }
//        return new String(s);
//    }
//}
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String s = sc.next();// 第一个分数
//            Rational r1 = new Rational(Rational.paraseNumerator(s),Rational.paraseDenominator(s));
//            s = sc.next();// 第一个分数
//            Rational r2 = new Rational(Rational.paraseNumerator(s),Rational.paraseDenominator(s));
//            System.out.println(r1 + " + " + r2 + " = " + r1.add(r2));
//            System.out.println(r1 + " - " + r2 + " = " + r1.sub(r2));
//            System.out.println(r1 + " * " + r2 + " = " + r1.mul(r2));
//            System.out.println(r1 + " / " + r2 + " = " + r1.div(r2));
//        }
//        sc.close();
//    }
//}

// 抄送列表
//public class Main {
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		while(sc.hasNext()){
//            String str1 = sc.nextLine();
//            String str2 = sc.nextLine();
//            char[] str1Arr = str1.toCharArray();
//            int len = str1Arr.length;
//            List<String> list =  new ArrayList<>();
//            StringBuffer s = new StringBuffer();
//            int count = 0;
//            for(int i = 0;i <len;i++){
//                char ch =  str1Arr[i];
//                if(ch == '"'){
//                    count++;
//                }else{
//                    if(count == 1){
//                        s.append(ch);
//                    }else if(count == 0){
//                        if(ch == ','){
//                            list.add(s.toString());
//                            s = new StringBuffer();
//                        }else{
//                            s.append(ch);
//                        }
//                    }
//                }
//                if(count == 2){
//                    list.add(s.toString());
//                    s = new StringBuffer();
//                    count=0;
//                    i++;
//                }else if(i == len-1){
//                    list.add(s.toString());
//                }
//
//            }
//            boolean flag = false;
//            for(int i = 0; i < list.size();i++){
//                if(list.get(i).equals(str2)){
//                    flag = true;
//                    System.out.println("Ignore");
//                    break;
//                }
//            }
//            if(!flag){
//                System.out.println("Important!");
//            }
//        }
//        sc.close();
//	}
//}

// 年终抽奖
//public class Main {
//    public static void main(String[] args){
//        long[] d = new long[21];
//        d[0] = 0;
//        d[1] = 0;
//        d[2] = 1;
//        long[] f = new long[21];
//        f[0] = 1;
//        f[1] = 1;
//        f[2] = 2;
//        for(int i=3;i < 21;i++){
//            d[i] =(i-1) * (d[i-1] + d[i-2]);
//            f[i] = f[i-1] * i;
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int  n = sc.nextInt();
//            System.out.printf("%.2f%%\n",100.0 * d[n] / f[n]);
//        }
//        sc.close();
//    }
//}

// 养兔子
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        long[] fib = new long[91];
//        fib[0] = 1;
//        fib[1] = 1;
//        for(int i = 2;i < 91;i++){
//            fib[i] = fib[i-1] + fib[i-2];
//        }
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            System.out.println(fib[n]);
//        }
//        sc.close();
//    }
//}


// 收件人列表
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = Integer.parseInt(sc.nextLine());
//            for(int i = 0;i < n;i++){
//                String str = sc.nextLine();
//                if(str.contains(" ") || str.contains(",")){
//                    System.out.print("\"" + str +"\"");
//                }else{
//                    System.out.print(str);
//                }
//                if(i == n-1){
//                    System.out.println();
//                }else{
//                    System.out.print(", ");
//                }
//            }
//        }
//        sc.close();
//    }
//}

// 客似云来
//public class Main{
//    public static void main(String[] ages){
//        long[] fib = new long[81];
//        fib[1] = 1;
//        fib[2] = 1;
//        for(int i = 3;i < 81;i++){
//            fib[i] = fib[i -1] + fib[i-2];
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int f = sc.nextInt();
//            int t = sc.nextInt();
//            long num = 0;
//            for(int i = f ;i <= t;i++){
//                num += fib[i];
//            }
//            System.out.println(num);
//        }
//        sc.close();
//    }
//}

// 剪花布条
// 使用库函数方法
////public class Main{
////    public static void main(String[] args){
////        Scanner sc = new Scanner(System.in);
////        while(sc.hasNext()){
////            String s = sc.next();
////            String t = sc.next();
////            int count = 0;
////            while(s.contains(t)){
////                s = s.replaceFirst(t,"");
////                count++;
////            }
////            System.out.println(count);
////        }
////    }
////}
// 贪心算法
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String s = sc.next();
//            String t = sc.next();
//            System.out.println(cut(s,t));
//        }
//        sc.close();
//    }
//    public static int cut(String s,String t){
//        int i = s.indexOf(t);
//        if(i == -1){
//            return 0;
//        }
//
//        return  1 + cut(s.substring(i+t.length()),t);
//    }
//}



// 斐波那契数凤尾
//import java.util.*;
//public class Main {
//    public static void main(String[] args){
//        int border = -1;
//        long[] ans = new long[100000];
//        ans[0] = 1;
//        ans[1] = 2;
//        for(int i =2;i< 100000;i++){
//            long next = ans[i-1] + ans[i-2];
//            if(border == -1 && next >=1000000){
//                border = i+1;
//            }
//            ans[i] = next % 1000000 ;
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(border >= n){
//               System.out.println(ans[n-1]);
//            }else{
//
//                System.out.printf("%06d\n",ans[n-1]);
//            }
//
//        }
//        sc.close();
//    }
//}

// 淘宝网店
//public class Main {
//    private static boolean isLeapYear(int y){
//        return y % 400 ==0 ||(y % 4 == 0 && y % 100 != 0);
//    }
//    private static int  profitofyear(int y){
//        return 2 * 31
//            + 1 * 28
//            + 1 * 31
//            + 2 * 30
//            + 1 * 31
//            + 2 * 30
//            + 1 * 31
//            + 2 * 31
//            + 2 * 30
//            + 2 * 31
//            + 1 * 30
//            + 2 * 31
//            + (isLeapYear(y) ? 1 : 0);
//    }
//    private static boolean isPrime(int m){
//        return m == 2 || m == 3 || m == 5 || m == 7 || m == 11;
//    }
//
//    private static int profitofThisYear(int y,int m,int d){
//        int profit = 0;
//        if(!isPrime(m)){
//            profit = d * 2;
//        }else{
//            profit = d;
//        }
//        while(--m > 0){
//            switch(m){
//                case 1: case 8: case 10: case 12:
//                    profit += 62;
//                    break;
//                case 3: case 5: case 7:
//                    profit += 31;
//                    break;
//                case 4: case 6: case 9:
//                    profit += 60;
//                    break;
//                case 11:
//                    profit += 30;
//                    break;
//                default:
//                    profit +=(28 + (isLeapYear(y) ? 1 : 0));
//                    break;
//            }
//        }
//        return profit;
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        int y1,m1,d1,y2,m2,d2;
//        int  profit = 0;
//        while(sc.hasNext()){
//            y1 = sc.nextInt();
//            m1 = sc.nextInt();
//            d1 = sc.nextInt();
//            y2 = sc.nextInt();
//            m2 = sc.nextInt();
//            d2 = sc.nextInt();
//            profit = profitofyear(y1) - profitofThisYear(y1,m1,d1-1);
//            profit += profitofThisYear(y2,m2,d2);
//            if(y1  == y2){
//                profit -= profitofyear(y1);
//            }
//            for(int i = y1 + 1;i < y2;i++){
//                profit += profitofyear(i);
//            }
//            System.out.println(profit);
//        }
//        sc.close();
//    }
//}


// 分解因数
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int a = sc.nextInt();
//            List<String> factors = factoruzation(a);
//            System.out.printf("%d = %s\n",a,String.join(" * ",factors));
//        }
//        sc.close();
//    }
//    private static List<String> factoruzation(int a){
//        List<String> ans = new ArrayList<>();
//        for(int i = 2;a >1 && i * i <= a ;i++){
//            while(a % i == 0){
//                a = a / i;
//                ans.add(String.valueOf(i));
//            }
//        }
//        if(a > 1){
//            ans.add(String.valueOf(a));
//        }
//        return ans;
//    }
//}

// 美国节日
//public class Main {
//    private static boolean isLeapYear(int y){
//        return (y % 400 == 0) || (y % 4 == 0 && y % 100 != 0);
//    }
//
//    private static final int[] DAYS={31,28,31,30,31,30,31,31,30,31,30,31};
//    public static int nDay(int y,int m,int d){
//        int n = d;
//        for(int i = 0;i < m-1;i++){
//            n += DAYS[i];
//        }
//        if(m > 2 && isLeapYear(y)){
//            n++;
//        }
//        return n;
//    }
//
//    private static int diff(int y,int m,int d){
//        return (y-1) + (y-1)/4 - (y-1)/100 + (y-1)/400 + nDay(y,m,d);
//    }
//
//    private static int week(int y,int m,int d){
//        int w = diff(y,m,d) % 7;
//        if(w == 0){
//            w = 7;
//        }
//        return w;
//    }
//
//    private static int m1(int w,int n,int e){
//        return  1 + (n - 1) * 7 + (7 - w + e) %  7;
//    }
//
//    private static int m2(int w){
//        int d = (w == 1 ? 7 : w-1);
//        return 32 - d;
//    }
//
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNextInt()){
//            int y = sc.nextInt();
//            System.out.printf("%d-01-01\n",y);
//            int w;
//            w = week(y,1,1);
//            System.out.printf("%d-01-%02d\n",y,m1(w,3,1));
//
//            w = week(y,2,1);
//            System.out.printf("%d-02-%02d\n",y,m1(w,3,1));
//
//            w = week(y,6,1);
//            System.out.printf("%d-05-%02d\n",y,m2(w));
//
//            System.out.printf("%d-07-04\n",y);
//
//            w = week(y,9,1);
//            System.out.printf("%d-09-%02d\n",y,m1(w,1,1));
//
//            w = week(y,11,1);
//            System.out.printf("%d-11-%02d\n",y,m1(w,4,4));
//
//            System.out.printf("%d-12-25\n",y);
//
//            System.out.println();
//
//        }
//        sc.close();
//    }
//}

// 因子个数
//public class Main {
//    public static void main(String[] str){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            System.out.println(factor(n));
//        }
//        sc.close();
//    }
//    public static int factor(int n){
//        int ret = 0;
//        for(int i = 2;i*i <= n;i++){
//            if( n % i == 0){
//                while(n % i == 0){
//                    n /= i;
//                }
//                ret++;
//            }
//        }
//        if(n != 1){
//            ret++;
//        }
//        return ret;
//    }
//}


// 最难的问题
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            StringBuffer s = new StringBuffer();
//            for(int i = 0;i < str.length();i++){
//                char ch =  str.charAt(i);
//                if(ch == ' '){
//                    s.append(" ");
//                }else{
//                    s.append( (char)(ch > 'E' ? ch-5 : ch + 21) );
//                }
//            }
//            System.out.println(s);
//        }
//        sc.close();
//    }
//}

// 有假币
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new  Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n == 0) break;
//            int count =0;
//            while(n > 1){
//                count++;
//                n =(int) Math.ceil((double)n/3);
//            }
//            System.out.println(count);
//        }
//        sc.close();
//    }
//}

// 求正整数数据的最小不可能组成和
//public class Solution {
//	/**
//	 *	正数数组中的最小不可组成和
//	 *	输入：正数数组arr
//	 *	返回：正数数组中的最小不可组成和
//	 */
//	public int getFirstUnFormedNum(int[] arr) {
//        int min = Integer.MAX_VALUE;
//        int max = 0;
//        for(int i : arr){
//            min = Math.min(min,i);
//            max +=i;
//        }
//        boolean[] result = new boolean[max+1];
//        result[0] = true;
//        for(int o : arr){
//            for(int j = max; j >=o;j--){
//                result[j] = result[j-o] || result[j];
//            }
//        }
//        for(int j = min;j < result.length;j++){
//            if(!result[j]){
//                return j;
//            }
//        }
//        return max+1;
//	}
//}

// 猴子分桃
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n == 0){
//                break;
//            }
//            long a = (long)(Math.pow(5,n) - 4);
//            long b = (long)(Math.pow(4,n) + n - 4);
//            System.out.println(a + " "+ b);
//        }
//        sc.close();
//    }
//}

// 反转部分单向链表
//class Node{
//    int val;
//    Node next;
//    public Node(int val){
//        this.val = val;
//    }
//}
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            Node head = new Node(-1);
//            Node tail = head;
//            for(int i = 0;i < n;i++){
//                Node node = new Node(sc.nextInt());
//                tail.next = node;
//                tail = node;
//            }
//            int left = sc.nextInt();
//            int right =  sc.nextInt();
//            Node newHead = reversePartList(head.next,left,right);
//            while(newHead != null){
//                System.out.print(newHead.val + " ");
//                newHead = newHead.next;
//            }
//        }
//        sc.close();
//    }
//    public static Node reversePartList(Node head,int left,int right){
//        Node tmpHead = new Node(-1);
//        tmpHead.next = head;
//        Node prev = tmpHead;
//        for(int i = 1;i < left;i++){
//            prev = prev.next;
//        }
//        Node cur = prev.next;
//        for(int i = left; i < right;i++){
//            Node tmp = cur.next;
//            cur.next = tmp.next;
//            tmp.next = prev.next;
//            prev.next = tmp;
//        }
//        return tmpHead.next;
//    }
//}

// 三角形
//import java.util.*;
//import java.math.*;
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            BigDecimal a = sc.nextBigDecimal();
//            BigDecimal b = sc.nextBigDecimal();
//            BigDecimal c = sc.nextBigDecimal();
//            if( a.add(b).compareTo(c) <=0 || a.add(c).compareTo(b) <= 0 ||  b.add(c).compareTo(a) <= 0){
//                System.out.println("No");
//            }else{
//                System.out.println("Yes");
//            }
//        }
//        sc.close();
//    }
//}

// 不用加减乘除做加法
//public class Solution {
//    public int Add(int num1,int num2) {
//        while(num2 != 0){
//            int tmp = num1 ^ num2;
//            num2 = (num1 & num2) << 1;
//            num1 = tmp;
//        }
//        return num1;
//    }
//}

// 数根
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            while(str.length()>1){
//                int sum = 0;
//                for(int i = 0;i < str.length();i++){
//                    sum += str.charAt(i) - '0';
//                }
//                str = String.valueOf(sum);
//            }
//            System.out.println(str);
//        }
//        sc.close();
//    }
//}

// 星际密码
//public class Main {
//    public static void main(String[] args){
//        int[] nums = new int[10001];
//        nums[1] = 1;
//        nums[2] = 2;
//        for(int i = 3;i < 10001;i++){
//            nums[i] = (nums[i-1] + nums[i-2])%10000;
//        }
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            StringBuffer s  = new StringBuffer();
//            for(int i = 0;i < n;i++){
//                int xi = sc.nextInt();
//                s.append(String.format("%04d",nums[xi]));
//            }
//            System.out.println(s);
//        }
//        sc.close();
//    }
//}

// 迷宫问题
//class Node{
//    int x;
//    int y;
//    public Node(int x,int y){
//        this.x = x;
//        this.y = y;
//    }
//}
//public class Main{
//    public static void  main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int m = sc.nextInt();
//            int[][] mat = new int[n][m];
//            for(int i = 0;i < n;i++){
//                for(int j = 0;j < m;j++){
//                    mat[i][j] = sc.nextInt();
//                }
//            }
//            // 搜索最短路径
//            ArrayList<Node> path = new ArrayList<>();
//            ArrayList<Node> minPath = new ArrayList<>();
//            int[][] book = new int[n][m];
//            getMinPath(mat,n,m,0,0,book,path,minPath);
//            // 打印最短路径
//            for(Node node : minPath){
//                System.out.println("(" + node.x + "," + node.y +")");
//            }
//
//        }
//        sc.close();
//    }
//    // mmt： 迷宫矩阵： row, col
//    // x，y：当前位置
//    // book：标记矩阵，标记当前位置是否走过
//    // path：保存当前走过的路径
//    // minPath：记录最短路径
//    public static void getMinPath(int[][] mat,int row,int col,int x,int y,int[][] book,ArrayList<Node> path,ArrayList<Node> minPath){
//        // 判断 x，y  是否越界，是否走过，是否有障碍
//        if(x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1 || mat[x][y] == 1){
//            return;
//        }
//        // 把当前位置存入路径
//        path.add(new Node(x,y));
//        // 标记当前位置
//        book[x][y] = 1;
//        // 判断 当前位置是否为出口
//        if(x == row -1 && y == col-1){
//            // 一条新路径的产生,需要判断是否为更短的路径
//            if(minPath.isEmpty() ||  path.size() < minPath.size()){
//                // 更新最短路径
//                minPath.clear();
//                for(Node n : path){
//                    minPath.add(n);
//                }
//            }
//        }
//        // 没到出口，就继续搜索（x，y）的上下左右四个方向
//        getMinPath(mat,row,col,x+1,y,book,path,minPath);
//        getMinPath(mat,row,col,x-1,y,book,path,minPath);
//        getMinPath(mat,row,col,x,y-1,book,path,minPath);
//        getMinPath(mat,row,col,x,y+1,book,path,minPath);
//        // 把当前位置从路径中删除，寻找新路径
//        path.remove(path.size()-1);
//        book[x][y] = 0;
//    }
//}

//年终奖
//public class Bonus {
//    public int getMost(int[][] board) {
//        for(int i = 1;i < 6;i++){
//            board[0][i] += board[0][i-1];
//        }
//        for(int i = 1;i < 6;i++){
//            board[i][0] += board[i-1][0];
//        }
//        for(int i = 1;i < 6;i++){
//            for(int j = 1;j < 6;j++){
//                board[i][j] += Math.max(board[i-1][j],board[i][j-1]);
//            }
//        }
//        return board[5][5];
//    }
//}

// 计算字符串的编辑距离
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new  Scanner(System.in);
//        while(sc.hasNext()){
//            String str1 = sc.nextLine();
//            String str2 = sc.nextLine();
//            if(str1.length() < str2.length()){
//                System.out.println(getDistance(str1,str2));
//            }else{
//                System.out.println(getDistance(str2,str1));
//            }
//        }
//        sc.close();
//    }
//    public static int getDistance(String str1,String str2){
//        char[] c1 = str1.toCharArray();
//        char[] c2 = str2.toCharArray();
//        int l1  = c1.length;
//        int l2 = c2.length;
//        int[][] dis = new int[l1 + 1][l2 + 1];
//        for(int i = 0;i <= l1;i++){
//            dis[i][0] = i;
//        }
//        for(int i = 0;i <= l2;i++){
//            dis[0][i] = i;
//        }
//        for(int i = 1;i <= l1;i++){
//            for(int j = 1;j <= l2;j++){
//                dis[i][j] = Math.min(dis[i-1][j],dis[i][j - 1] ) + 1;
//                if(c1[i-1] == c2[j-1]){
//                    dis[i][j] = Math.min(dis[i][j],dis[i-1][j-1]);
//                }else{
//                     dis[i][j] = Math.min(dis[i][j],dis[i-1][j-1]+1);
//                }
//            }
//        }
//        return dis[l1][l2];
//    }
//}


// 微信红包
//public class Gift {
//    public int getValue(int[] gifts, int n) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for(int i = 0;i < n;i++){
//            Integer tmp = map.get(gifts[i]);
//            map.put(gifts[i],tmp == null ? 1 : tmp + 1);
//        }
//        int i = 0;
//        for(;i < n;i++){
//            if(map.get(gifts[i]) > n/2){
//                return gifts[i];
//            }
//        }
//        return 0;
//
//    }
//}

// 找出字符串中第一个只出现一次的字符
// 数组计数
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            char[] ch = sc.nextLine().toCharArray();
//            int[] count = new int[123 - 'a'];
//            for(int i = 0;i < ch.length;i++){
//                count[ch[i] - 'a']++;
//            }
//            int i = 0;
//            for(;i < ch.length;i++){
//                if(count[ch[i] - 'a'] == 1){
//                    System.out.println(ch[i]);
//                    break;
//                }
//            }
//            if(i == ch.length) System.out.println(-1);
//        }
//        sc.close();
//    }
//}

//哈希表
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            char[] ch = sc.nextLine().toCharArray();
//            HashMap<Character,Integer> map =  new HashMap<>();
//            for(int i = 0;i < ch.length;i++){
//                Integer tmp = map.get(ch[i]);
//                map.put(ch[i],tmp == null? 1 : tmp+1);
//            }
//            int i = 0;
//            for(;i < ch.length;i++){
//                if(map.get(ch[i]) == 1){
//                    System.out.println(ch[i]);
//                    break;
//                }
//            }
//            if(i == ch.length)
//            System.out.println(-1);
//        }
//        sc.close();
//    }
//}

// 小易的升级之路
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int a = sc.nextInt();
//            int[] arr = new int[n];
//            for(int i = 0;i < n;i++){
//                arr[i] = sc.nextInt();
//            }
//            for(int i = 0;i < n;i++){
//                if(a >= arr[i]){
//                    a += arr[i];
//                }else{
//                    a += getNum(arr[i],a);
//                }
//            }
//            System.out.println(a);
//
//        }
//        sc.close();
//    }
//    public static int getNum(int a,int b){
//        int carry = a % b;
//        while(carry != 0){
//            a = b;
//            b = carry;
//            carry = a % b;
//        }
//        return b;
//    }
//}


// MP3 光标位置
//import java.util.*;
//public class Main{
//    public static void mouseMove(String numStr,String orderStr){
//        //歌曲数量
//        int n = Integer.parseInt(numStr);
//        // 指令数组
//        char[] order = orderStr.toCharArray();
//        // 当前鼠标的位置
//        int mouse = 1;
//        // 显示列表所在的起始位置
//        int first = 1;
//        // 指令处理
//        // 歌曲的数量小于等 4
//        if(n <= 4){
//            // 循环处理每一个指令
//            for(int i = 0;i < order.length;i++){
//                if(mouse == 1 && order[i] == 'U'){
//                    mouse = n;
//                }else if(mouse == n && order[i] == 'D'){
//                    mouse = 1;
//                }else if(order[i] == 'U'){
//                    mouse--;
//                }else if(order[i] == 'D'){
//                    mouse++;
//                }
//            }
//            for(int i = 1;i < n;i++){
//                System.out.printf(i + " ");
//            }
//            System.out.println(n);
//            System.out.println(mouse);
//        }else{
//            for(int i = 0;i < order.length;i++){
//                if(first == 1 && mouse == 1 && order[i] == 'U'){
//                    mouse = n;
//                    first = n-3;
//                }else if((first == n -3) && mouse == n && order[i] == 'D'){
//                    first = 1;
//                    mouse = 1;
//                }else if(order[i] == 'U' && first != 1 && mouse == first){
//                    mouse--;
//                    first--;
//                }else if(order[i] == 'D' && mouse == first+3 && first != n-3){
//                    mouse++;
//                    first++;
//                }else if(order[i] == 'D'){
//                    mouse++;
//                }else if(order[i] == 'U'){
//                    mouse--;
//                }
//            }
//            for(int i = first;i < first+3;i++){
//                System.out.printf(i + " ");
//            }
//            System.out.println(first+3);
//            System.out.println(mouse);
//        }
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String num = sc.nextLine();
//            String orders = sc.nextLine();
//            mouseMove(num,orders);
//        }
//        sc.close();
//    }
//}


//洗牌
//import java.util.*;
//public class Main{
//    public static void plauCard(int[] cards,int n,int k){
//        for(int i = 0;i < k;i++){
//            int[] newCards = new int[cards.length];
//            for(int j = 0;j < n;j++){
//                newCards[2 * j] = cards[j];
//                newCards[2 * j + 1] = cards[j+n];
//            }
//            cards = newCards;
//        }
//        printCard(cards);
//    }
//    public static void printCard(int[] arr){
//        for(int i = 0;i < arr.length-1;i++){
//            System.out.printf(arr[i] + " ");
//        }
//         System.out.println(arr[arr.length-1]);
//    }
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int t = sc.nextInt();
//            for(int i = 0;i < t;i++){
//                int n = sc.nextInt();
//                int k = sc.nextInt();
//                int[] cards = new int[n*2];
//                for(int j = 0;j < 2 * n;j++){
//                    cards[j] = sc.nextInt();
//                }
//                plauCard(cards,n,k);
//            }
//        }
//        sc.close();
//    }
//}

// 公共子串计算
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String m = sc.nextLine();
//            String s = sc.nextLine();
//            if(m!=null || s != null){
//                if(m.length() > s.length()){
//                    System.out.println(getMaxSubLen(s,m));
//                }else{
//                    System.out.println(getMaxSubLen(m,s));
//                }
//            }
//
//        }
//        sc.close();
//    }
//    public static int getMaxSubLen(String m,String n){
//        char[] arrm = m.toCharArray();
//        int lenm = arrm.length;
//        char[] arrn = n.toCharArray();
//        int lenn = arrn.length;
//        int max = 0;
//        int[][] arr = new int[lenm+1][lenn+1];
//        for(int i = 1; i <= lenm;i++){
//            for(int j = 1;j <= lenn;j++){
//                if(arrm[i-1] == arrn[j-1]){
//                    arr[i][j] = arr[i-1][j-1] + 1;
//                    if(max < arr[i][j]){
//                        max = arr[i][j];
//                    }
//                }
//            }
//        }
//        return  max;
//    }
//}

// 查找两个字符串 a，b 中的最长公共子串
//public class Main {
//    public static void main(String[] agrs){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String major = sc.nextLine();
//            String sub = sc.nextLine();
//            if(major != null || sub != null){
//                if(major.length() < sub.length()){
//                    System.out.println(getMaxSubstring(major,sub));
//                }else{
//                    System.out.println(getMaxSubstring(sub,major));
//                }
//            }
//
//        }
//        sc.close();
//    }
//    public static String getMaxSubstring(String str1,String str2){
//        char[] arr1 = str1.toCharArray();
//        char[] arr2 = str2.toCharArray();
//        int l1 = arr1.length;
//        int l2 = arr2.length;
//        int startL = 0;
//        int maxL = 0;
//        int[][] maxSub = new int[l1 +1][l2 + 1];
//        for(int i = 1;i <= l1;i++){
//            for(int j = 1;j <= l2;j++){
//                if(arr1[i-1] == arr2[j-1]){
//                    maxSub[i][j] = maxSub[i-1][j-1] + 1;
//                    if(maxL < maxSub[i][j]){
//                        maxL = maxSub[i][j];
//                        startL = i - maxL;
//                    }
//                }
//            }
//        }
//        return str1.substring(startL,startL + maxL);
//    }
//}

//汽水瓶
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if( n != 0){
//                System.out.println(getNum(n));
//            }
//
//
//        }
//        sc.close();
//    }
//    public static int getNum(int num){
//        int sum  = 0;
//        while(num > 1){
//            sum += num/3;
//            num = num/3 + num % 3;
//            if(num == 2){
//                sum++;
//                break;
//            }
//        }
//        return sum;
//    }
//}


//字符串通配符
//import java.util.*;
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String t = sc.nextLine();
//            String s = sc.nextLine();
//            System.out.println(match(t,s));
//        }
//        sc.close();
//    }
//    public static boolean match(String s1,String s2){
//        char[] c1 = s1.toCharArray();
//        char[] c2 = s2.toCharArray();
//        int l1 = c1.length;
//        int l2 = c2.length;
//        boolean[][] dp = new boolean[l2+1][l1+1];
//        dp[0][0] = true;
//        for(int i = 0;i <= l2;i++){
//            for(int j = 1;j <= l1;j++){
//                if(c1[j-1] == '*'){
//                    if(i == 0){
//                        dp[i][j] = dp[i][j-1];
//                    }else{
//                        if(c2[i-1] == '.' || Character.isLetter(c2[i-1]) || Character.isDigit(c2[i-1])){
//                            dp[i][j] = dp[i-1][j] || dp[i][j-1];
//                        }
//                    }
//                }else{
//                    if(i>0 && defs(c1[j-1],c2[i-1])){
//                        dp[i][j] = dp[i-1][j-1];
//                    }
//                }
//            }
//        }
//        return dp[l2][l1];
//    }
//    public static boolean defs(char c1,char c2){
//        if( c1 == '?') return true;
//        if(c1 >= 'a' && c1 <= 'z'){
//            c1 = (char)(c1 - 'a' + 'A');
//        }
//        if(c2 >= 'a' && c2 <= 'z'){
//            c2 = (char)(c2 - 'a' + 'A');
//        }
//        return c1 == c2;
//    }
//}



// 每个月兔子的总数
// import java.util.*;
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            System.out.println(num(n));
//
//        }
//        sc.close();
//    }
//    public static int num(int m){
//        int first  = 1;
//        int second = 1;
//        int sum = 1;
//        for(int i = 3;i <= m;i++){
//            sum = first + second;
//            first = second;
//            second = sum;
//        }
//        return sum;
//    }
//}


//杨辉三角的变形
// 找规律做法
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            if(n < 3){
//                System.out.println(-1);
//            }else{
//                if(n % 4 == 0){
//                    System.out.println(3);
//                }else if(n % 2 == 1){
//                    System.out.println(2);
//                }else{
//                    System.out.println(4);
//                }
//            }
//
//        }
//        sc.close();
//    }
//}



// 完全数计算
//import java.util.*;
//public class Main {
//    public static void  main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            int n = sc.nextInt();
//            int count = 0;
//            for(int i = 2;i <= n;i++){
//                int sum = 0;
//                for(int j = 2; j * j <= i;j++){
//                    if(i % j == 0){
//                        if(i / j == j){
//                            sum += j;
//                        }else{
//                            sum += j + i/j;
//                        }
//                    }
//                }
//                if(sum + 1 == i){
//                    count++;
//                }
//            }
//            System.out.println(count);
//        }
//        sc.close();
//    }
//}


// 扑克牌大小
//import java.util.*;
//public class Main {
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//        while(sc.hasNext()){
//            String str = sc.nextLine();
//            String[] poker = str.split("-");
//            String[] p1 = poker[0].split(" ");
//            String[] p2 = poker[1].split(" ");
//            String p ="34567891JQKA2";
//            if(poker[0].equals("joker JOKER") || poker[1].equals("joker JOKER")  ){
//                System.out.println("joker JOKER");
//            }else if(p1.length == p2.length){
//                if(p.indexOf(p1[0].substring(0,1)) > p.indexOf(p2[0].substring(0,1))){
//                    System.out.println(poker[0]);
//                }else{
//                    System.out.println(poker[1]);
//                }
//            }else if(p1.length == 4){
//                System.out.println(poker[0]);
//            }else if(p2.length == 4){
//                System.out.println(poker[1]);
//            }else{
//                System.out.println("ERROR");
//            }
//        }
//        sc.close();
//    }
//}
